//enum Rotation { Left, Right }  
//fn rotate_node(node: &mut TreeNode, dir: Rotation) { /* TODO */ }  
//#[test] fn test_rotation() { /* 检查高度平衡 */ }  

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
    height: i32,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
            height: 1,
        }
    }

    // 右旋转（处理LL型不平衡）
    fn rotate_right(mut node: Box<Self>) -> Box<Self> {
        let mut new_root = node.left.take().unwrap();
        node.left = new_root.right.take();
        new_root.right = Some(node);
        
        // 更新高度（需实现height计算方法）
        new_root.height = new_root.calc_height();
        new_root
    }

    // 左旋转（处理RR型不平衡）
    fn rotate_left(mut node: Box<Self>) -> Box<Self> {
        let mut new_root = node.right.take().unwrap();
        node.right = new_root.left.take();
        new_root.left = Some(node);
        
        new_root.height = new_root.calc_height();
        new_root
    }

    // 计算节点高度
    fn calc_height(&self) -> i32 {
        1 + self.left_height().max(self.right_height())
    }

    // 辅助方法
    fn left_height(&self) -> i32 {
        self.left.as_ref().map_or(0, |n| n.height)
    }

    fn right_height(&self) -> i32 {
        self.right.as_ref().map_or(0, |n| n.height)
    }
}

#[test]
fn test_rotation() {
    // 构建左偏树
    let mut root = TreeNode::new(3);
    root.left = Some(Box::new(TreeNode::new(2)));
    root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(1)));
    
    // 执行右旋
    let rotated = TreeNode::rotate_right(Box::new(root));
    assert_eq!(rotated.val, 2);
    assert_eq!(rotated.right.as_ref().unwrap().val, 3);
}

// AVL树可视化演示
fn main() {
    // 初始状态
    let mut node = Box::new(TreeNode::new(3));
    node.left = Some(Box::new(TreeNode::new(2)));
    node.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(1)));
    println!("Before rotation:\n{:?}", node);

    // 执行旋转
    let rotated = TreeNode::rotate_right(node);
    println!("\nAfter right rotation:\n{:?}", rotated);
}